1. Technical Field
The present invention relates in general to a system and method for solving a large system of dense linear equations. In particular, the present invention relates to a system and a method for solving a large system of linear equations using a system having multiple processing units with a common memory for sharing data.
2. Description of the Related Art
Many problems from many disciplines can be modeled using a system of linear equations. Linear equations, for example, may be used to obtain solutions for problems in physics, chemistry, engineering, computer science, etc.
Small systems of linear equations (systems with only a few variables) can be solved by eliminating all but one variable, for which a solution is obtained. Variable elimination involves multiplying each equation by a constant or adding or subtracting one equation from another. Once one variable has been determined, the other unknown variables may be computed by back substitution.
A system of linear equations has a corresponding matrix equation. The solution to this equivalent matrix equation is the same as the solution to the system of linear equations, and therefore, a solution to a system of linear equations may be obtained by obtaining a solution to the equivalent matrix equation.
A large system of linear equations is typically solved by obtaining a solution to the equivalent matrix equation. Numerically, it is more efficient to obtain a solution to the matrix equation. Efficient methods for solving the matrix equation include, for example, LU decomposition and Gauss elimination. The processes involve the exchanging of large amount of data between the processors since the results are interdependent.
Thus, there is a need for a fast and accurate system and method for solving large systems of dense linear equations using multiple processors. The system and method should provide for fast and easy sharing of data results between the different processors to avoid the inefficient transmissions of large amount of data.